/**
 * Software License, Version 1.0
 * 
 * Copyright 2003 The Trustees of Indiana University. All rights reserved.
 * 
 * 
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 * 
 * 1) All redistributions of source code must retain the above copyright notice,
 * the list of authors in the original source code, this list of conditions and
 * the disclaimer listed in this license; 2) All redistributions in binary form
 * must reproduce the above copyright notice, this list of conditions and the
 * disclaimer listed in this license in the documentation and/or other materials
 * provided with the distribution; 3) Any documentation included with all
 * redistributions must include the following acknowledgement:
 * 
 * "This product includes software developed by the Community Grids Lab. For
 * further information contact the Community Grids Lab at
 * http://communitygrids.iu.edu/."
 * 
 * Alternatively, this acknowledgement may appear in the software itself, and
 * wherever such third-party acknowledgments normally appear.
 * 
 * 4) The name Indiana University or Community Grids Lab or NaradaBrokering,
 * shall not be used to endorse or promote products derived from this software
 * without prior written permission from Indiana University. For written
 * permission, please contact the Advanced Research and Technology Institute
 * ("ARTI") at 351 West 10th Street, Indianapolis, Indiana 46202. 5) Products
 * derived from this software may not be called NaradaBrokering, nor may Indiana
 * University or Community Grids Lab or NaradaBrokering appear in their name,
 * without prior written permission of ARTI.
 * 
 * 
 * Indiana University provides no reassurances that the source code provided
 * does not infringe the patent or any other intellectual property rights of any
 * other entity. Indiana University disclaims any liability to any recipient for
 * claims brought by any other entity based on infringement of intellectual
 * property rights or otherwise.
 * 
 * LICENSEE UNDERSTANDS THAT SOFTWARE IS PROVIDED "AS IS" FOR WHICH NO
 * WARRANTIES AS TO CAPABILITIES OR ACCURACY ARE MADE. INDIANA UNIVERSITY GIVES
 * NO WARRANTIES AND MAKES NO REPRESENTATION THAT SOFTWARE IS FREE OF
 * INFRINGEMENT OF THIRD PARTY PATENT, COPYRIGHT, OR OTHER PROPRIETARY RIGHTS.
 * INDIANA UNIVERSITY MAKES NO WARRANTIES THAT SOFTWARE IS FREE FROM "BUGS",
 * "VIRUSES", "TROJAN HORSES", "TRAP DOORS", "WORMS", OR OTHER HARMFUL CODE.
 * LICENSEE ASSUMES THE ENTIRE RISK AS TO THE PERFORMANCE OF SOFTWARE AND/OR
 * ASSOCIATED MATERIALS, AND TO THE PERFORMANCE AND VALIDITY OF INFORMATION
 * GENERATED USING SOFTWARE.
 */
package cgl.narada.protocol;

import java.util.Enumeration;
import java.util.Hashtable;
import java.util.Vector;

import cgl.narada.util.ByteUtilities;

/**
 * For a given node, this class maintains a cache of the links (from this node)
 * that are the best links to send an event over to reach its destinations as
 * computed by the profile info, and contained within the routing information
 * that the event contains.
 * 
 * The cache needs to be updated during link/node failures, since some if not
 * all the entries could be invalidated by such an <i>event</i>. The cache
 * would once again be updated during the node organization protocol.
 * 
 * This class is implemented as a thread which waits on any updates on the
 * gatewayInfo class, and upon receiving a notification recomputes the routing
 * cache.
 * 
 * @author Shrideep Pallickara $Revision$ $Date$
 */

public class RoutingCache implements ProtocolDebugFlags {

    private GatewayInfo gateway;

    /**
     * The number of keys within the routing cache corresponds to the number of
     * open connections originating from this node.
     */
    private Hashtable routingCache;

    /**
     * This keeps track of the destinations that can be reached from any hop in
     * the connectivity graph
     */
    private Hashtable destinationDirectory;

    /**
     * This hashtable maintains the list of destinations that can be reached
     * fastest from a given hop.
     */
    private Hashtable bestDestinationsFromHop;

    private int systemLevel;

    private String moduleName = "RoutingCache: ";

    /**
     * The routing cache constructor. The system level is needed for the
     * creation of destinations associated with a hop, besides other reasons.
     * 
     * @param gateway -
     *            The gatewayInfo for the server node.
     * @param systemLevel -
     *            The system level
     */
    public RoutingCache(GatewayInfo gateway, int systemLevel) {
        this.gateway = gateway;
        this.systemLevel = systemLevel;
        routingCache = new Hashtable();
        destinationDirectory = new Hashtable();

        bestDestinationsFromHop = new Hashtable();
    }

    /**
     * This updates the routing cache with the best hop that needs to be taken
     * to reach the node in question. These nodes which we refer to, are the
     * nodes in the connectivity graph
     * 
     * @param nodeToReach -
     *            The node that needs to be reached
     * @param bestHop -
     *            The best hop that can be taken from the server node in
     *            question to reach <i>nodeToReach</i>
     */
    public void updateRoutingInformation(Gateway nodeToReach, Gateway bestHop) {
        if (routingCache.containsKey(nodeToReach)) {
            routingCache.remove(nodeToReach);
        }
        routingCache.put(nodeToReach, bestHop);
        if (destinationDirectory.containsKey(bestHop)) {
            Destinations _destinationDirectoryVal = ((Destinations) destinationDirectory
                .get(bestHop));
            _destinationDirectoryVal.updateDestinationList(nodeToReach);
            return;
        }
        System.out.println("RoutingCache:: Destination directory entry for "
            + bestHop + " not found");
    }

    /**
     * This method returns the best hop that needs to be taken to reach a given
     * node
     * 
     * @param nodeToReach -
     *            Is the (node+level) gateway node that needs to be reached in
     *            the connectivity graph.
     */
    public Gateway getBestHopToReachNode(Gateway nodeToReach) {
        if (routingCache.containsKey(nodeToReach)) {
            return (Gateway) routingCache.get(nodeToReach);
        }
        /**
         * This indicates that there are no hops thatcan be taken to reach this
         * particular node ... one of the reasons this could be the case is that
         * the unit in question is partitioned
         */
        return null;
    }

    /**
     * Returns the destinations that can be reached fastest from the specified
     * hop.
     * 
     * @param hop
     * @return
     */
    public Destinations getFastestDestinationsFromHop(Gateway hop) {
        Destinations _destinations = null;
        if (destinationDirectory.containsKey(hop)) {
            _destinations = ((Destinations) destinationDirectory.get(hop));
        }
        return _destinations;
    }

    public Gateway[] computeHopsToReachDestination(
                                                   Destinations destinationToReach,
                                                   Destinations traversedSoFar) {
        Gateway[] hopsToTake = null;
        Vector hopVector = new Vector();
        Destinations tryToReach = new Destinations(systemLevel);

        for (int i = 0; i <= systemLevel; i++) {
            tryToReach.setDestinationsAtLevel(i, destinationToReach
                .getDestinationsAtLevel(i));
        }

        /** Compute the true set of destinations that need to be reached */
        removeFromDestinationList(tryToReach, traversedSoFar);

        /** See if hops can be used to fast track some destinations */
        Gateway[] hops = gateway.getHops();

        if (hops == null) {
            return hopsToTake;
        }

        if (hops.length == 0) {
            if (RoutingCache_Debug) {
                System.out.println(moduleName
                    + "There are no hops for this node");
            }
        }

        for (int i = 0; i < hops.length; i++) {
            Destinations fastTracked = destinationsReachedFromHop(hops[i]);
            boolean canBeFastTracked = checkIfDestinationsCanBeFastTracked(
                                                                           tryToReach,
                                                                           fastTracked);

            if (canBeFastTracked) {
                if (RoutingCache_Debug) {
                    System.out.println(moduleName + "Fast track over hop "
                        + hops[i]);
                }
                removeFromDestinationList(tryToReach, fastTracked);
                hopVector.addElement(hops[i]);
            } else {
                if (RoutingCache_Debug) {
                    System.out.println(moduleName + "NO Fast track over hop "
                        + hops[i]);
                }
            }
        }

        hopsToTake = new Gateway[hopVector.size()];
        hopVector.copyInto(hopsToTake);
        return hopsToTake;

    }

    private void removeFromDestinationList(Destinations destinationToReach,
                                           Destinations traversedSoFar) {
        int[] toReach = destinationToReach.getDestinationsInInts();
        int[] traversed = traversedSoFar.getDestinationsInInts();

        /**
         * System.out.print("\n\t\t["); for (int i=0; i <=systemLevel; i++) {
         * System.out.print(toReach[i] + "(" + i + ") "); }
         * System.out.println("]\n");
         * 
         * System.out.print("\n\t\t["); for (int i=0; i <=systemLevel; i++) {
         * System.out.print(traversed[i] + "(" + i + ") "); }
         * System.out.println("]\n");
         */

        for (int i = 0; i <= systemLevel; i++) {

            // System.out.println("\t"+ ByteUtilities.printInt(toReach[i]) +
            // "\t(" + i + ")" +
            // "\n\t" + ByteUtilities.printInt(traversed[i]));
            int newToReach = toReach[i]
                & ByteUtilities.performNotOperation(traversed[i]);
            // System.out.println("\t" + ByteUtilities.printInt(newToReach) +
            // "\n\n");
            toReach[i] = newToReach;
        }

    }

    private boolean 
    checkIfDestinationsCanBeFastTracked(Destinations tryToReach,
                                        Destinations fastTracked) {
        if (fastTracked == null) {
            return false;
        }
        int[] reachDests = tryToReach.getDestinationsInInts();
        int[] fastTrack = fastTracked.getDestinationsInInts();

        boolean canReach = false;
        for (int i = 0; i <= systemLevel; i++) {
            int andValue = reachDests[i] & fastTrack[i];
            if (andValue != 0) {
                canReach = true;
                return canReach;
            }

        }
        return canReach;
    }

    /**
     * This method returns a list of hops that can be employed to reach our
     * destinations. This method performs several checks.
     * <ul>
     * <li>The hops that are returned are those which have a <i>reachability</i>
     * to at least one of the destinations that need to be reached.
     * <li>Also if a given hop can satisfy all the destinations that need to be
     * reached only that hop is returned.
     * <li>This method traverses through the destinations directory till such
     * time that no more destinations need to reached.
     * </ul>
     * The hops that are considered in the preliminary list of hops that can
     * used for reaching destinations are the list of hops that have not already
     * been traversed.
     * 
     * @param destinationToReach
     *            The destinations that need to be reached.
     * @param traversedSoFar
     *            The destinations that have been reached so far.
     * 
     * @return The hops that can be taken to reach the destinations. This return
     *         value could be null if there are no hops that can be employed to
     *         reach <i>any</i> of the destinations that are contained in
     *         <i>destinationToReach</i>
     */
    public Gateway[] hopsToReachDestination(Destinations destinationToReach,
                                            Destinations traversedSoFar) {
        // System.out.println("To Reach " + destinationToReach +
        // " Reached So far " + traversedSoFar );
        Vector hopVector = new Vector();
        Destinations _cannotReach;

        /*
         * if (destinationToReach.equals(traversedSoFar)) { return null; }
         */

        for (Enumeration e = destinationDirectory.keys(); e.hasMoreElements();) {
            Gateway hop = (Gateway) e.nextElement();
            if (!hop.containedInRoutingInformation(traversedSoFar)) {
                if (RoutingCache_Debug)
                    System.out
                        .println("RoutingCache:: Inside hops enumeration loop");
                Destinations _dest = (Destinations) destinationDirectory
                    .get(hop);
                _cannotReach = _dest
                    .computeDestinationsThatCannotBeReached(destinationToReach);
                if (_cannotReach.equals(destinationToReach)) {
                    /** None of the destinations can be reached using this hop */
                    System.out
                        .println("RoutingCache: No destination can be reached");
                    // System.out.println("Destinations reached by hop " + hop +
                    // " -> " + _dest);
                    continue;
                }

                if (_cannotReach.equals(new Destinations(systemLevel))) {
                    /** i.e. there are no destinations that cannot be reached */
                    if (RoutingCache_Debug)
                        System.out
                            .println("RoutingCache: All destinations can be "
                                + "reached");
                    hopVector.addElement(hop);
                    break;
                }
                /**
                 * If the program control reaches here it implies that some if
                 * not all destinations could be reached using this hop
                 */
                hopVector.addElement(hop);
                if (RoutingCache_Debug)
                    System.out.println("RoutingCache: Some destinations can be"
                        + " reached");
                destinationToReach.updateWithDestination(_cannotReach);

            }/* end-if */

        } /* end-for */

        if (hopVector.size() == 0) {
            /**
             * This means that there are no hops that can be taken to reach the
             * set of destinations, so stop trying to route this event
             */
            return null;
        }

        Gateway[] retArray = new Gateway[hopVector.size()];
        hopVector.copyInto(retArray);
        return retArray;
    }

    /**
     * Provides the destinations that can be reached from a hop. The
     * destinations are returned as a node address.
     * 
     * @param gateway -
     *            The hop from the server node hosting the connectivity graph.
     * @return The destinations that can be reached from this hop, if it is a
     *         valid hop. Otherwise return null.
     * 
     */
    public Destinations destinationsReachedFromHop(Gateway gateway) {
        if (destinationDirectory.containsKey(gateway)) {
            return (Destinations) destinationDirectory.get(gateway);
        }
        /**
         * gateway is not a valid hop, and thus contains no entry in the
         * destinationDirectory
         */
        System.out.println("RoutingCache: The gateway " + gateway
            + " is not a valid hop");
        return null;
    }

    /** This method adds a hop to the destination directory */
    public synchronized void addHop(Gateway hop) {
        if (destinationDirectory.containsKey(hop)) {
            System.out.println("RoutingCache->addHop() : Gateway " + hop
                + " already present in destinationDirectory");
            return;
        }
        System.out.println("RoutingCache->addHop() : Gateway " + hop);
        destinationDirectory.put(hop, new Destinations(systemLevel));

        bestDestinationsFromHop.put(hop, new Destinations(systemLevel));
    }

    /** This method removes a hop from the destination directory */
    public synchronized void removeHop(Gateway hop) {
        if (destinationDirectory.containsKey(hop)) {
            destinationDirectory.remove(hop);
            System.out.println("RoutingCache->removeHop() : Gateway " + hop
                + " removed from destinationDirectory");
        } else {
            System.out.println("RoutingCache->removeHop() : Gateway " + hop
                + " not present in destinationDirectory");
        }

        if (bestDestinationsFromHop.containsKey(hop)) {
            bestDestinationsFromHop.remove(hop);
        }
    }

    /**
     * If a new connection at level <i>gatewayLevel</i> is added, destination
     * listings need to be computed for nodes at level <b>&nbsp;>= &nbsp;</b>
     * <i>gatewayLevel</i> in the connectivity graph. Thus for each hop we need
     * to invalidate the destinations that could be reached from a given hop.
     * This invalidation affects destinations <b>&nbsp;>= &nbsp;</b>
     * gatewayLevel for every hops destination list.
     * 
     * @param gatewayLevel -
     *            The destination level which needs to be invalidated.
     */
    public void invalidateDestinationDirectoryListings(int gatewayLevel) {
        for (Enumeration e = destinationDirectory.keys(); e.hasMoreElements();) {
            Destinations destinationAtHop = (Destinations) destinationDirectory
                .get(e.nextElement());
            destinationAtHop.invalidateDestinationsAtLevel(gatewayLevel);
        }
    }

    /**
     * A utility method which traverses the destinationDirectory and provides a
     * listing of the destinations at each level (within the connectivity graph)
     * that can be reached by evry hop that originates from the vertex node
     */
    public void performDestinationDirectoryListing() {
        for (Enumeration e = destinationDirectory.keys(); e.hasMoreElements();) {
            Gateway g = (Gateway) e.nextElement();
            Destinations destinationAtHop = (Destinations) destinationDirectory
                .get(g);
            System.out.println("Destinations reached from hop->" + g + " are "
                + destinationAtHop);
        }
    }

    public static void main(String[] args) {
    }

}
